/*
 *  Copyright (c) 2012 Shirou Maruyama
 * 
 *   Redistribution and use in source and binary forms, with or without
 *   modification, are permitted provided that the following conditions
 *   are met:
 * 
 *   1. Redistributions of source code must retain the above Copyright
 *      notice, this list of conditions and the following disclaimer.
 *
 *   2. Redistributions in binary form must reproduce the above Copyright
 *      notice, this list of conditions and the following disclaimer in the
 *      documentation and/or other materials provided with the distribution.
 *
 *   3. Neither the name of the authors nor the names of its contributors
 *      may be used to endorse or promote products derived from this
 *      software without specific prior written permission.
 */

#ifndef MULTIKEY_QSORT_HPP_
#define MULTIKEY_QSORT_HPP_

#include <vector>
#include <string>
#include <stdint.h>

namespace cpi00 {

  void MultikeyQsort(std::vector<std::string>& strs, 
                     const uint64_t low, const uint64_t num, 
                     const uint64_t depth) {
    if (num <= 1) return;
    uint8_t pivot = 
      static_cast<uint8_t>(strs[low + num - 1][depth]);
    uint64_t m0 = 0, m1 = 0, m2 = 0;
    for (uint64_t i = low, j = i; i < low + num; ++i) {
      if (strs[i].size() <= depth) {
        strs[i].swap(strs[j]);
        ++j; ++m0;
      }
    }
    for (uint64_t i = low + m0, j = i; i < low + num; ++i) {
      if (pivot > static_cast<uint8_t>(strs[i][depth])) {
        strs[i].swap(strs[j]);
        ++j; ++m1;
      }
    }
    for (uint64_t i = low + m0 + m1, j = i; i < low + num; ++i) {
      if (pivot == static_cast<uint8_t>(strs[i][depth])) {
        strs[i].swap(strs[j]);
        ++j; ++m2;
      }
    }
    MultikeyQsort(strs, low + m0,  m1, depth);
    MultikeyQsort(strs, low + m0 + m1, m2, depth + 1);
    MultikeyQsort(strs, low + m0 + m1 + m2, num - (m0 + m1 + m2), depth);
  }

  bool IsSorted(const std::vector<std::string>& strs) {
    for (uint64_t i = 1; i != strs.size(); ++i) {
      if (strs[i].compare(strs[i-1]) < 0) {
        return false;
      }
    }
    return true;
  }

} // namespace cpi00

#endif // MULTIKEY_QSORT_HPP_
